/**
 * 单词搜索
 *
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如
 * 果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格
 * 是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 * 示例 1：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 *
 * 示例 2：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
 * 输出：true
 *
 * 示例 3：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
 * 输出：false
 *
 * 提示：
 * m == board.length
 * n = board[i].length
 * 1 <= m, n <= 6
 * 1 <= word.length <= 15
 * board 和 word 仅由大小写英文字母组成
 *
 *
 * 进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
 */



/**
 * 我们只要遍历每一个位置就可以了, 判断我们 board 数组的每一个
 * 位置是否满足 深搜的第一个条件(与 word 的第一个字符相同) 满足
 * 就开始这个位置的深搜, 这个位置要深搜 4 次, 分别是他旁边的 4
 * 个, 这里可以进行一点优化, 就是但我们上一个位置寂静深搜成功,
 * 我们就不用继续向下进行深搜了, 别忘了我们不能走之前走过的路径
 * 所以我们要搞一个 数组对一次深搜的走过的路径进行 记录
 * 时间复杂度 : O(m * n * 4 ^ L)
 * 空间复杂度 : O(m ^ n)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word = "SEE";
        System.out.println(test.exist(board, word));
    }

    // 全局变量
    char[] words;
    boolean[][] tmp;
    int m;
    int n;
    boolean ret = false;

    public boolean exist(char[][] board, String word) {

        // 初始化
        words = word.toCharArray();
        m = board.length;
        n = board[0].length;
        tmp = new boolean[m][n];

        // 遍历每一个位置
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                // 判断与第一个数是否相同, 并且这个位置要是没有走过的
                if (board[i][j] == words[0] && !tmp[i][j]) {

                    // 进行深搜前标记这个位置
                    tmp[i][j] = true;

                    // 深搜
                    dfs(1, i, j, board);

                    // 恢复现场
                    tmp[i][j] = false;

                    // 这里也可以进行一点小优化, 要是已经成功找到路径
                    // 直接返回 true
                    if (ret) {
                        return true;
                    }
                }
            }
        }

        // 没有找到返回 false
        return false;
    }

    /**
     *
     * @param k 当前 word 的位置
     * @param i 本次深搜原位置
     * @param j
     * @param board 原数组
     */
    private void dfs (int k, int i, int j, char[][] board) {

        // 要是满足条件, 返回即可
        if (k == words.length) {
            ret = true;
            return;
        }

        // 这里要避免越界, 和要保证和 word 的第 k 个
        // 字符和此次深搜的位置相同, 还要保证你 这个是
        // 没有走过的路径
        if (i - 1 >= 0
                && board[i - 1][j] == words[k]
                && !tmp[i - 1][j]) {

            // 标记路径
            tmp[i - 1][j] = true;

            dfs(k + 1, i - 1, j, board);

            // 恢复现场
            tmp[i - 1][j] = false;
        }

        // 这里进行优化, 要是已经找到了成功路径, 直接返回
        if (ret) {
            return;
        }

        if (i + 1 < m
                && board[i + 1][j] == words[k]
                && !tmp[i + 1][j]) {

            tmp[i + 1][j] = true;
            dfs(k + 1, i + 1, j, board);
            tmp[i + 1][j] = false;
        }

        if (ret) {
            return;
        }

        if (j - 1 >= 0
                && board[i][j - 1] == words[k]
                && !tmp[i][j - 1]) {

            tmp[i][j - 1] = true;
            dfs(k + 1, i, j - 1, board);
            tmp[i][j - 1] = false;
        }

        if (ret) {
            return;
        }

        if (j + 1 < n
                && board[i][j + 1] == words[k]
                && !tmp[i][j + 1]) {

            tmp[i][j + 1] = true;
            dfs(k + 1, i, j + 1, board);
            tmp[i][j + 1] = false;
        }

    }
}